﻿using System;
using System.Collections.Generic;
using Microsoft.Xna.Framework;

namespace AttrapeMoi
{
    class Djikstra
    {
        public static Vector2 Direction1(Vector2 depa, Vector2 arri, Carte carte)
        {
            int[,] matrice_adj = carte.Matrice_adjacence;
            Coord arr = new Coord(arri.X, arri.Y);
            Coord dep = new Coord(depa.X, depa.Y);
            Sommet[,] sommets = new Sommet[carte.Longueur_y, carte.Longueur_x];
            bool impossible = false; ;
            for (int i = 0; i < carte.Longueur_y; i++)
            {
                for (int j = 0; j < carte.Longueur_x; j++)
                {
                    if (carte.getCase(j, i).Contenu1 != Contenu.inexistant && carte.getCase(j, i).Contenu1 != Contenu.gendarme)
                        sommets[i, j] = new Sommet();
                }
            }
            sommets[dep.Y, dep.X] = new Sommet();

            sommets[arr.Y, arr.X].Potentiel = 0;
            Coord current = arr;
            // faire le test sur les coordonnées pour voir
            //Algo de recherche
            while (current != dep && !impossible)
            {
                Sommet z = sommets[current.Y, current.X];
                z.Marque = true;

                List<int> liste_dir = new List<int>();
                int numCase = carte.getCase(current.X, current.Y).NumCase;
                for (int i = 0; i < carte.Longueur_adjacence; i++)
                {
                    if (matrice_adj[i, numCase] == 1)
                        liste_dir.Add(i);
                }

                foreach (int i in liste_dir)
                {
                    Coord caseAEtudier = new Coord(carte.getCase(i).Position.X, carte.getCase(i).Position.Y);
                    if (sommets[caseAEtudier.Y, caseAEtudier.X] != null)
                    {
                        Sommet s = sommets[caseAEtudier.Y, caseAEtudier.X];
                        if (s.Potentiel > z.Potentiel + 1)
                        {
                            s.Potentiel = z.Potentiel + 1;
                            s.Pred = current;
                        }
                    }
                }

                int min = Sommet.INFINI-1;

                List<Coord> current_potentiel = new List<Coord>();

                if (sommets[dep.Y, dep.X].Potentiel < Sommet.INFINI)
                    current = dep;
                else
                {
                    Coord ancien = current;

                    for (int i = 0; i < carte.Longueur_y; i++)
                    {
                        for (int j = 0; j < carte.Longueur_x; j++)
                        {
                            if (sommets[i, j] != null)
                            {
                                if (!sommets[i, j].Marque && sommets[i, j].Potentiel <= min)
                                {

                                    if (sommets[i, j].Potentiel < min)
                                    {
                                        current_potentiel.Clear();
                                        min = sommets[i, j].Potentiel;
                                    }
                                        

                                    current_potentiel.Add(new Coord(j, i));
                                }
                            }
                        }
                    }

                    if (current_potentiel.Count > 1)
                    {
                        bool change = false;
                        Coord ca = new Coord(0, 0);
                        if (Math.Abs(dep.X - arr.X) > Math.Abs(dep.Y - arr.Y))
                            if (dep.X > arr.X)
                                ca = new Coord(-1, 0);
                            else
                                ca = new Coord(1, 0);
                        else
                            if (dep.Y > arr.Y)
                                ca = new Coord(0, -1);
                            else
                                ca = new Coord(0, 1);

                        foreach (Coord c in current_potentiel)
                        {
                            if (dep + ca == c)
                            {
                                current = c;
                                change = true;
                            }
                        }

                        if (!change)
                        {
                            Random aleatoire = new Random();
                            int a = aleatoire.Next(current_potentiel.Count);
                            current = current_potentiel[a];
                        }
                    }
                    else
                        current = current_potentiel[0];

                    if (current.X == ancien.X && current.Y == ancien.Y)
                        impossible = true;
                }
            }

            Coord next;

            if (!impossible)// donc current == dep
                //if (sommets[current.Y, current.X].Pred != dep)//  on veut son prédecesseur uniquement si les deux cases ne sont pas cote a cote
                next = sommets[current.Y, current.X].Pred;
            else
            {
                Vector2 t = new Vector2(arr.X - dep.X, arr.Y - dep.Y);

                if (Math.Abs(t.X) > Math.Abs(t.Y))
                {
                    if (t.X > 0)
                        next = new Coord(dep.X + 1, dep.Y);
                    else
                        next = new Coord(dep.X - 1, dep.Y);
                }
                else
                {
                    if (t.Y > 0)
                        next = new Coord(dep.X, dep.Y + 1);
                    else
                        next = new Coord(dep.X, dep.Y - 1);
                }
            }
                
            /*
             if (sommets[current.Y, current.X].Pred == null)
                next = current;
             else
                next = sommets[current.Y, current.X].Pred;
                */
             return new Vector2(next.X, next.Y); 
        }
        
        public static Sommet[,] Coloration(Carte carte, Vector2 depa)
        {
            int[,] matrice_adj = carte.Matrice_adjacence;
            Coord dep = new Coord(depa.X, depa.Y);
            Sommet[,] sommets = new Sommet[carte.Longueur_y, carte.Longueur_x];
            bool impossible = false; ;
            for (int i = 0; i < carte.Longueur_y; i++)
            {
                for (int j = 0; j < carte.Longueur_x; j++)
                {
                    if (carte.getCase(j, i).Contenu1 != Contenu.inexistant && carte.getCase(j, i).Contenu1 != Contenu.gendarme)
                        sommets[i, j] = new Sommet();
                }
            }

            sommets[dep.Y, dep.X] = new Sommet();
            sommets[dep.Y, dep.X].Potentiel = 0;
            Coord current = dep;
            // faire le test sur les coordonnées pour voir
            //Algo de recherche
            while (!impossible)
            {
                Sommet z = sommets[current.Y, current.X];
                z.Marque = true;

                List<int> liste_dir = new List<int>();
                int numCase = carte.getCase(current.X, current.Y).NumCase;
                for (int i = 0; i < carte.Longueur_adjacence; i++)
                {
                    if (matrice_adj[i, numCase] == 1)
                        liste_dir.Add(i);
                }

                foreach (int i in liste_dir)
                {
                    Coord caseAEtudier = new Coord(carte.getCase(i).Position.X, carte.getCase(i).Position.Y);
                    if (sommets[caseAEtudier.Y, caseAEtudier.X] != null)
                    {
                        Sommet s = sommets[caseAEtudier.Y, caseAEtudier.X];
                        if (s.Potentiel > z.Potentiel + 1)
                        {
                            s.Potentiel = z.Potentiel + 1;
                            s.Pred = current;
                        }
                    }
                }

                int min = Sommet.INFINI;

                Coord ancien = current;

                for (int i = 0; i < carte.Longueur_y; i++)
                {
                    for (int j = 0; j < carte.Longueur_x; j++)
                    {
                        if (sommets[i, j] != null)
                        {
                            if (!sommets[i, j].Marque && sommets[i, j].Potentiel < min)
                            {
                                min = sommets[i, j].Potentiel;
                                current = new Coord(j, i);
                            }
                        }
                    }
                }

                if (current.X == ancien.X && current.Y == ancien.Y)
                    impossible = true;
            }

            return sommets;
        }
    }  
}